package alg20241117;

import java.util.Arrays;
import java.util.Random;


public class Text2 {
    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(0,stock.length - 1, stock, cnt);
        return Arrays.copyOf(stock, cnt);
    }
    public void qsort(int l, int r, int[] stock, int cnt){
        if(l >= r) return;
        int left = l - 1, right = r + 1, i = l;
        int key = stock[new Random().nextInt(r - l + 1) + l];
        while(i < right){
            if(stock[i] < key) swap(++left, i++, stock);
            else if(stock[i] == key) i++;
            else swap(--right, i, stock);
        }
        //[l left]  [left + 1, right - 1]  [right, r]
        int a = left - l + 1;
        int b = right - left - 1;
        if(a >= cnt) qsort(l, left, stock, cnt);
        else if(a + b >= cnt) return;
        else qsort(right, r, stock, cnt - a - b);
    }
    public void swap(int i, int j, int[] nums){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
